package com.wc.alorithm_blue_bridge._数学知识.约数.Q1460;

import java.util.Arrays;

/**
 * @Author congge
 * @Date 2023/10/12 19:10
 * @description 路径
 * https://www.lanqiao.cn/problems/1460/learning/?page=2&first_category_id=1&sort=students_count&second_category_id=3
 */
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
//        int ans = Integer.MAX_VALUE;
        int n = 2021;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[1] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (Math.abs(j - i) > 21) {
                    break;
                } else {
                    dp[j] = Math.min(dp[j], dp[i] + i * j / main.gcd(i, j));
                }
            }
        }

        System.out.println(dp[n]);
    }

    public int gcd(int num1, int num2) {
        if (num1 > num2) {
            return gcd(num2, num1);
        }
        while (num2 % num1 != 0) {
            num2 = num2 % num1;
            num1 = num2 + num1;
            num2 = num1 - num2;
            num1 = num1 - num2;
        }

        return num1;
    }
}
